Search results for "Cartesian product"
showing 7 items of 7 documents
Restricted compositions and permutations: from old to new Gray codes
2011
Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let @? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of @? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that @? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval si…
ℓ-distant Hamiltonian walks in Cartesian product graphs
2009
Abstract We introduce and study a generalisation of Hamiltonian cycles: an l-distant Hamiltonian walk in a graph G of order n is a cyclic ordering of its vertices in which consecutive vertices are at distance l. Conditions for a Cartesian product graph to possess such an l-distant Hamiltonian walk are given and more specific results are presented concerning toroidal grids.
Completely independent spanning trees in some regular graphs
2014
International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…
Strong chromatic index of products of graphs
2007
Graphs and Algorithms
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
2006
A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…
Homogeneous Weyl connections of non-positive curvature
2015
We study homogenous Weyl connections with non-positive sectional curvatures. The Cartesian product $\mathbb S^1 \times M$ carries canonical families of Weyl connections with such a property, for any Riemmanian manifold $M$. We prove that if a homogenous Weyl connection on a manifold, modeled on a unimodular Lie group, is non-positive in a stronger sense (streched non-positive), then it must be locally of the product type.
Radio k-Labelings for Cartesian Products of Graphs
2005
International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…